package leetcode.code1054;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

import leetcode.helper.H;

public class Solution {

	public int[] rearrangeBarcodes(int[] barcodes) {
		int len = barcodes.length;
		Map<Integer, Integer> map = new HashMap<>();
		for (int i : barcodes) {
			map.put(i, map.getOrDefault(i, 0) + 1);
		}
		PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[0] - a[0]);
		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
			queue.add(new int[] { entry.getValue(), entry.getKey() });
		}
		int[] ans = new int[len];
		int[] cur = queue.poll();
		ans[0] = cur[1];
		if (--cur[0] > 0) {
			queue.add(cur);
		}
		for (int i = 1; i < len; i++) {
			cur = queue.poll();
			if (cur[1] == ans[i - 1]) {
				int[] next = queue.poll();
				ans[i] = next[1];
				if (--next[0] > 0) {
					queue.add(next);
				}
				queue.add(cur);
			} else {
				ans[i] = cur[1];
				if (--cur[0] > 0) {
					queue.add(cur);
				}
			}
		}
		return ans;
	}

	public int[] rearrangeBarcodes1(int[] barcodes) {
		int len = barcodes.length;
		Arrays.sort(barcodes);
		int[] ans = new int[len];
		int k = (len + 1) / 2;
		for (int i = 0, j = 0; i < len; i += 2, j++) {
			ans[i] = barcodes[j];
			if (i + 1 < len)
				ans[i + 1] = barcodes[j + k];
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.rearrangeBarcodes(H.str2array3("[1,1,1,2,2,2]"));
	}
}
